The present invention relates to facsimile data compression and more particularly relates to encoding and decoding apparatus and methods for shortening transmission times of binary facsimile data.
Facsimile systems which convert images of document originals into electrical signal and reconvert the signals into document copies are used on an increasingly widespread basis for document copy transmission via the standard telephone communications network. Electro-optical devices such as photodiodes are used to scan a document original along adjacent sequentially parallel scan lines. The light and dark areas of the document produce analogous electrical signals at the photo device, and these signals are shaped into binary format and then typically converted into a frequency modulated aural signal which is coupled directly into standard voice grade telephone circuits for transmission to a compatible facsimile receiver/reproducer at a distance. Depending upon such factors as the scan rate, horizontal and vertical resolution, signal format, etc., transmission times of such units have ranged from, e.g., one to twenty minutes per letter size page of document to be sent. For facsimile users having numerous pages of documents to send over long distance telephone circuits, the tolls on such calls have been the predominant cost and have impeded more widespread adoption and use of facsimile by business and government alike.
One prior art technique for reduction of the transmission times of facsimile data in binary format has been run length encoding. In that scheme each scan line was divided into a fairly substantial number of individual segments (e.g., 61 bits). Each scan line was made up of alternating stretches of zeros or ones, corresponding to light and dark regions along the scan line. By the run length encoding scheme, each unbroken stretch of zeros or ones was encoded by counting and sending only the number of zero or one segments therein. For example, one scan line might have had 4 white segments (picture elements, also known and referred to as "pixels") followed by 8 black segments, followed by 7 white segments, followed by 3 black segments, followed by 13 white segments, followed by 10 black segments, followed by 4 white segments, followed by 14 white segments, for a total of 61 segments and eight stretches for the entire line. Hexadecimal binary encoding of the number of segments for each stretch provided a run length code of 32 binary places for the eight stretches. Thus, for the foregoing example, run length encoding provided data reduction of almost two to one 32 binary places in lieu of 61). While a two to one data compression would reduce actual transmission time in half, a need for substantially greater data compression ratios has arisen to reduce further the overall transmission times and resultant long distance telephone system toils.